package com.bubaiwantong.algorithms.exchange;

/**
 * @author bubaiwantong
 * @description
 */
public class QuickSort {

    public static void main(String[] args) {
        /*
            快速排序算法
         */
        int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        QuickSort quickSort = new QuickSort();
        quickSort.print(arr);
        quickSort.sort(arr, 0, arr.length - 1);
        quickSort.print(arr);

    }


    public void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int q = partition(arr, left, right);
        sort(arr, left, q - 1);
        sort(arr, q + 1, right);
    }


    int partition(int[] arr, int left, int right) {
        int temp = arr[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            while (i <= j && arr[i] <= temp) {
                i++;
            }
            while (i <= j && arr[j] > temp) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
        }
        swap(arr,left,j);
        return j;
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
